[蓝桥杯]历届试题(1)

注：所有答案可在 在线编程，代码在线运行，在线写代码工具 (dotcpp.com) 在线编译，带数据输入输出。

题目 1004: [递归]母牛的故事

题目描述

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

输入格式

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

输出格式

对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

样例输入

1
2
3
4
2
4
5
0 //0表示结束

样例输出

1
2
3
2
4
6

解题思路:

​ 第n年的母牛的来源分别来自于前一年剩下的和往前推3年的母牛（能生的母牛，最早的也算在里面）

第一年 第二年 第三年 第四年 第五年 第六年
1 2 3 4 4(第四年)+2(第二年)=6f(5-1) + f(5-3) = 6f(4) + f(2) = 6 6(第五年)+3(第三年)=9f(6-1) + f(6-3) = 9f(5) + f(3) = 9

6 = 前一年剩下的4头牛+（第2年新产的母牛刚具有生育能力生下的1头+最早的母牛1头）
$$
解题公式：f(n) = f(n-1) + f(n-3)
$$

解法1 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            System.out.println(f(n));
        }
    }
     
    public static int f(int n){
        //前四天没有母牛出生
        if(n<=4){
            return n;
        }
        //上一天出生数加前三天的出生数
        return f(n-1)+f(n-3);
    }
}

解法2 记忆型递归+剪枝 避免计算重复子问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            System.out.println(f(n));
        }
    }
     
    public static Integer[] arr = new Integer[999];
    public static int f(int n){ 
        //前四天没有母牛出生       
        if(n<=4){
            arr[n]=n;
            return n;
        }
        //剪枝避免计算重复子问题
        if(arr[n]!=null){
            return arr[n];
        }
        //记住存储结果 以便复用
        arr[n]=f(n-1)+f(n-3);        
        return arr[n];
    }
}

解法3 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int [] arr = new int[999];
        while(true){
            int n = sc.nextInt();
            if(n==0)break;
            for(int i = 1;i <= n;i++ ){
                //前四天没有母牛出生    
                if(i<=4){
                    arr[i]=i;
                }else{
                    arr[i]=arr[i-1]+arr[i-3];
                }
            }
            System.out.println(arr[n]);
        }
    }
}

题目：成绩分析(真题)

题目描述

小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。

请计算这次考试的最高分、最低分和平均分。

输入描述

输入的第一行包含一个整数 n\ (1 ≤ n ≤ 10^4)n (1≤n≤104)，表示考试人数。

接下来 nn 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。

输出描述

输出三行。

第一行包含一个整数，表示最高分。

第二行包含一个整数，表示最低分。

第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。

样例输入

1
2
3
4
5
6
7
8
7 //第一行为测试人数
80
92
56
74
88
99
10

样例输出

1
2
3
99
10
71.29

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int testNumber = scan.nextInt(); //捕捉第一行测试人数作循环次数
        double average = 0;
        int max = 0;
        int min = 100;
        int nextNum = 0;
        int count = 0;
        while(testNumber>0){
            nextNum = scan.nextInt();
            average += nextNum;
            count ++;
            testNumber --;
            if(nextNum > max) max = nextNum;
            if(nextNum < min) min = nextNum;
        }
        System.out.println(max);
        System.out.println(min);
        System.out.println(String.format("%.2f",average/count)); //输出平均分，保留两位小数
        scan.close();
    }
}

题目：成绩统计(真题)

小蓝给学生们组织了一场考试，卷面总分为 100 分，每个学生的得分都是一个 0 到 100 的整数。

如果得分至少是 60 分，则称为及格。如果得分至少为 85 分，则称为优秀。

请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整 数。

输入描述

输入的第一行包含一个整数 n\ (1 \leq n \leq 10^4)n (1≤n≤104)，表示考试人数。

接下来 nn 行，每行包含一个 0 至 100 的整数，表示一个学生的得分。

输出描述

输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分 四舍五入保留整数。

样例输入

1
2
3
4
5
6
7
8
7
80
92
56
74
88
100
0

样例输出

1
2
71%
43%

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Scanner;
import java.lang.*;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int nextNum = 0;
        double passCount = 0;
        double excelLentCount = 0;
        int numberOfPeople = scan.nextInt(); //接成绩数量
        for (int i = 0;i < numberOfPeople;i ++){
            nextNum = scan.nextInt();
            if(nextNum>=85) {
              excelLentCount ++;
              passCount ++;
            } else if(nextNum>=60) {
              passCount ++;
            }
        }
        System.out.println(Math.round(passCount*100/numberOfPeople)+"%"); //Math.round即四舍五入
        System.out.println(Math.round(excelLentCount*100/numberOfPeople)+"%"); //注:Math.round(Double)
        //乘以一百是因为原数据算完是小数点后两位，整形(int)表示为零
        scan.close();
    }
}

题目：单词分析(真题)(难度：简单)

题目描述

小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组 成，有些单词很长，远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得最多来分辨单词。

现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这 个字母出现的次数。

输入描述

输入一行包含一个单词，单词只由小写英文字母组成。

对于所有的评测用例，输入的单词长度不超过 1000。

输出描述

输出两行，第一行包含一个英文字母，表示单词中出现得最多的字母是哪 个。如果有多个字母出现的次数相等，输出字典序最小的那个。

第二行包含一个整数，表示出现得最多的那个字母在单词中出现的次数。

样例输入

1
longlonglongistoolong

样例输出

1
2
o
6

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str = scan.nextLine();
        
        int[] a = new int[26];//记录26个英文字母出现的次数，其中数组a的每个元素初始值为0
        for (int i = 0; i < str.length(); i++) {
          a[str.charAt(i)-'a']++; //str的第每个字符减去'a'的ASCII码，剩下的任何字母都在1-26内
        }

        char ch = 'a';
        int max = 0;
        for(int i=0;i<26;i++){
          if(a[i]>max){
            max=a[i]; //把数组a中最大的数字赋值给max，作为字母出现的次数
            ch=(char)('a'+i);/*把这个最大的数字在数组a中的顺序号
            加上a的ASCII码转为英文字符输出，
            即输出这个出现次数最多的应为字符*/
          }
        }
        System.out.println(ch);
        System.out.println(max);
        scan.close();
    }
}

题目： 购物单(真题)(填空题)

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。

这不，大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。

小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。

现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。

取款机只能提供 100100 元面额的纸币。小明想尽可能少取些现金，够用就行了。 你的任务是计算出，小明最少需要取多少现金。

以下是让人头疼的购物单，为了保护隐私，物品名称被隐藏了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
****     180.90       88折
****      10.25       65折
****      56.14        9折
****     104.65        9折
****     100.30       88折
****     297.15        半价
****      26.75       65折
****     130.62        半价
****     240.28       58折
****     270.62        8折
****     115.87       88折
****     247.34       95折
****      73.21        9折
****     101.00        半价
****      79.54        半价
****     278.44        7折
****     199.26        半价
****      12.97        9折
****     166.30       78折
****     125.50       58折
****      84.98        9折
****     113.35       68折
****     166.57        半价
****      42.56        9折
****      81.90       95折
****     131.78        8折
****     255.89       78折
****     109.17        9折
****     146.69       68折
****     139.33       65折
****     141.16       78折
****     154.74        8折
****      59.42        8折
****      85.44       68折
****     293.70       88折
****     261.79       65折
****      11.30       88折
****     268.27       58折
****     128.29       88折
****     251.03        8折
****     208.39       75折
****     128.88       75折
****      62.06        9折
****     225.87       75折
****      12.89       75折
****      34.28       75折
****      62.16       58折
****     129.12        半价
****     218.37        半价
****     289.69        8折

需要说明的是，8888 折指的是按标价的 88%88 计算，而 88 折是按 80%80 计算，余者类推。 特别地，半价是按 50%50 计算。

请输出小明要从取款机上提取的金额，单位是元。

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.ArrayList;
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
      Scanner scan = new Scanner(System.in);
      ArrayList<String> price = new ArrayList<String>();
      ArrayList<String> discount = new ArrayList<String>();
      for(int i = 0;i<50;i++){
        scan.next();//获取(跳过)每行的 ****
        price.add(scan.next()); //获取每行的价格，装载进动态数组price
        discount.add(scan.next()); //获取每行的折扣，装载进动态数组discount

        if(discount.get(i).length() == 2){ 
            //get(i)即获取动态数组kou中第i个元素中只有两个字符的元素(半价、9折、8折)
          if(discount.get(i).charAt(0) == '半') discount.set(i,"5"); 
            //动态数组[折扣]的每个元素第一个字符是'半'的，替换为'5'
          else if(discount.get(i).charAt(0) == '8') discount.set(i,"8"); 
            //第一个字符是8的，直接全部替换为8
          else discount.set(i,discount.get(i).charAt(0)+"");
        } else if(discount.get(i).length() == 3) { //如果折扣那列有三个字符(78折、65折、68折等)
          discount.set(i,discount.get(i).charAt(0)+""+discount.get(i).charAt(1));
            //只把前两个数字的字符取出
        }
    }

    int result = 0;
    for(int i=0;i<50;i++){
       result += Float.valueOf(price.get(i)/*获取价格*/) * (Float.valueOf/*把字符转为浮点数*/(discount.get(i)/*获取折扣(字符形)*/) > 10 ? (Float.valueOf(discount.get(i)))*0.01 :(Float.valueOf(discount.get(i)))*0.1);
    }                                                                                                    //如果大于10，就是有两个字符的折扣，如85，把它乘以0.01再计算。如果小于10就是一个字符的，如8、9把它乘以0.1再计算                                                                                   
    //System.out.println(result);//打印测试，得5110
    for(int i=100;i<100000;i+=100){ 
      if(result <= i) //简单的计数，i以每100计数并递增，当i比5110大时打印i并跳出循环
      {
        System.out.print(i);
        break;
      }
    }
  }
}

题目：门牌制作(真题)(填空题)(暴力)

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝要为一条街的住户制作门牌号。

这条街一共有 20202020 位住户，门牌号从 11 到 20202020 编号。

小蓝制作门牌的方法是先制作 00 到 99 这几个数字字符，最后根据需要将字符粘贴到门牌上，例如门牌 1017 需要依次粘贴字符 1、0、1、71、0、1、7，即需要 11 个字符 00，22 个字符 11，11 个字符 77。

请问要制作所有的 11 到 20202020 号门牌，总共需要多少个字符 22？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    public static void main(String[] args) {
      String s = "";
      int count = 0;
      for(int i=1;i<=2020;i++){
        s = String.valueOf(i); //String.valueOf() 将int转为String
        for(int j=0;j<s.length();j++){
          if(s.charAt(j) == '2') count++;
        }
      }
      System.out.println(count);
    }
}

题目：回文日期(真题)

题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020 年 2 月 2 日。因为如果将这个日期按 “yyyymmdd” 的格式写成一个 8 位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是 “千年一遇” 的特殊日子。对此小明很不认同，因为不到 2 年之后就是下一个回文日期：20211202 即 2021 年 12 月 2 日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即 2121 年 12 月 12 日。算不上 “千年一遇”，顶多算 “千年两遇”。

给定一个 8 位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入描述

输入包含一个八位整数 NN，表示日期。

对于所有评测用例，10000101 \leq N \leq 8999123110000101≤N≤89991231，保证 NN 是一个合法日期的 8 位数表示。

输出描述

输出两行，每行 1 个八位数。第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。

样例输入

输入

1
20200202

样例输出

1
2
20211202
21211212

我的解题(答案错误)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Main ma = new Main();
        Scanner scan = new Scanner(System.in);
        String str = scan.next();
        str = str.substring(0,4); //把输入的20200202，切剩前四个年份数字
        int strToValue = Integer.valueOf(str); //把年份字符串转为整形用作循环
        int year = Integer.valueOf(str);
        int thousand,hundred,ten,one;
        for(int i=strToValue+1;i<9000;i++){ 
          //如果用i=strToValue的话，测试20199102时，回文日期就会是20199102，和输入的一样
          thousand = i/1000; //取余到千位
          hundred = i/100%10; //取余到百位
          ten = i/10%10; //取余到十位
          one = i%10; //取余到个位
              if((ten+one)<13 && (thousand+hundred)<31 && /*这一段是要保证不是ABAB型*/ hundred != one){
              System.out.println(ma.paLindRomicDate(i));
              break;
              } 
        }
        for(int i=strToValue+1;i<9000;i++){   
          //如果用i=strToValue的话，ABAB型回文日期就会是20200202，和输入的一样
          thousand = i/1000; //取余到千位
          hundred = i/100%10; //取余到百位
          ten = i/10%10; //取余到十位
          one = i%10; //取余到个位          
              if(thousand == ten && hundred == one){
              System.out.print(ma.ABABpaLindRomicDate(i));
              break;
          }
        }      
        scan.close();
    }

    public int paLindRomicDate(int year){
      String yearStr = String.valueOf(year);//数字转为字符串，进行字符处理
      StringBuffer yearStrBf = new StringBuffer(8); //创建一个8宽度的StringBuffer
      StringBuilder revers = new StringBuilder(yearStr).reverse(); //用StringBuilder把字符串做反转
      yearStrBf.append(yearStr); //追加年份的字符
      yearStrBf.append(revers);  //追加年份的反转字符
      year = Integer.valueOf(yearStrBf.toString()/*先把StringBuffer转为String，然后再转为int*/);
      return year;
    }

    public int ABABpaLindRomicDate(int year){
      String yearStr = String.valueOf(year);//数字转为字符串，进行字符处理
      StringBuffer yearStrBf = new StringBuffer(8); //创建一个8宽度的StringBuffer
      StringBuilder revers = new StringBuilder(yearStr).reverse(); //用StringBuilder把字符串做反转
      String judgeMonth = (revers.toString().charAt(0)+""+revers.toString().charAt(1)); //必须加上双引号，不然字符加起来是ASCII码值
      String judgeDay = (revers.toString().charAt(2)+""+revers.toString().charAt(3));
      int judgeMonthtoValue = Integer.valueOf(judgeMonth);
      int judgeDaytoValue = Integer.valueOf(judgeDay);
      if(judgeMonthtoValue<13 && judgeDaytoValue<32){ //判断，必须月份小于13、日期小于31才合并回文日期
        yearStrBf.append(yearStr); //追加年份的字符
        yearStrBf.append(revers);  //追加年份的反转字符
        year = Integer.valueOf(yearStrBf.toString()/*先把StringBuffer转为String，然后再转为int*/);
      }
      return year;
    }
}

正确解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.time.LocalDate;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        //初始化日期
        int year = Integer.parseInt(str.substring(0, 4));
        int month = Integer.parseInt(str.substring(4, 6));
        int day = Integer.parseInt(str.substring(6, 8));
        LocalDate date = LocalDate.now();
        date = date.withYear(year);
        date = date.withMonth(month);
        date = date.withDayOfMonth(day);
        date = date.plusDays(1);

        String a = null;
        String b = null;
        boolean isFind = false;
        while (true) {
            String dateStr = date.toString().replace("-", "");
            if (isPalindromeDate(dateStr)) {
                if (!isFind) {
                    isFind = true;
                    a = dateStr;
                }
                if (isABABBABA(dateStr)) {
                    b = dateStr;
                    break;
                }
            }
            date = date.plusDays(1);
        }
        System.out.println(a);
        System.out.println(b);

        in.close();
    }

//判断是否是回文日期
    static boolean isPalindromeDate(String date) {
        for (int i = 0; i < date.length() / 2; i++) {
            if (date.charAt(i) != date.charAt(date.length() - 1 - i)) {
                return false;
            }
        }
        return true;
    }

//判断是否符合ABABBABA类型
    static boolean isABABBABA(String date) {
        char[] c = date.toCharArray();
        return c[0] == c[2] && c[2] == c[5] && c[5] == c[7] && c[1] == c[3] && c[3] == c[4] && c[4] == c[6];
    }
}

题目：货物摆放

题目描述

小蓝有一个超大的仓库，可以摆放很多货物。

现在，小蓝有 n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。

小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n = L x W x H

给定 n，请问有多少种堆放货物的方案满足要求。

例如，当 n = 4时，有以下 6 种方案：1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。

请问，当 n = 2021041820210418 （注意有 16 位数字）时，总共有多少种方案？

提示：建议使用计算机编程解决问题。

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.math.BigInteger;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
      ArrayList<Long> arr = new ArrayList<Long>();
      long num = 2021041820210418l;
      for(long i=1;i<=Math.sqrt(num);i++){
        if(num%i==0){
        arr.add(i);
        long n = num/i;
        if(n!=i){
          arr.add(n);
        }
      }
    }
    int count = 0;

    for(long i : arr){ //等效于long i=0;i<arr.size();i++，但是时间复杂度更低
      for(long j : arr){
        for(long k : arr){
          if(i * j * k == num) count++;
        }
      }
    }

    System.out.println(count);
  }
}

解析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.ArrayList;

public class Main {
    public static void main(String args[]) {

        //常规思路

        /*
        long num = 2021041820210418l;

        int count = 0;
        for ( long i = 1 ; i < num ; i++ ){
            for ( long j = 1 ; j < num ; j++ ){
                for ( long k = 1 ; k < num ; k++ ){
                    if ( i * j *um ){
                        count++;
                    }
                }
            }
        }
        */

        //显而易见，这个算法的时间复杂的非常的大。计算机想要算出结果，可能需要几天的时间

        //所以要另辟蹊径

        //想想，三个数相乘要等于num，那么这三个数是不是都是num的因子，都能被num整除呢？
        //上方的算法，三层for循环都是从1遍历到num，其中很多组合都是无效的
        //简而言之，这些无效组合中不能同时被num整除，而有效的组合，任何一个数都能被num整除
        //所以，如果我们能从num的因子里面去找组合，是不是时间复杂度就要小许多？

        long num = 2021041820210418l;
        //如果直接赋值,计算机默认数字是int类型，会报错。所以要在后面加'l'，转换为long类型

        //定义一个ArrayList数组，存放num的因子
        ArrayList<Long> arr = new ArrayList<>();

//从1开始遍历，遍历到num的平方根结束。不需要把num遍历一遍，这样算法复杂度也非常大，重点看for循环里面的语句
        for ( long i = 1 ; i <= Math.sqrt(num) ; i++ ){

            if ( num % i == 0 ){
                arr.add(i);     //如果能被整除，就放到arr数组中

                //！！！重点在这里，当i能被num整除的情况下，求出num关于i的另外一个除数n
                //这样，for循环不需要从1遍历到num。可以通过较小的因子，求出另外一个较大的因子
                long n = num / i;

        //如果num = Math.sqrt(num)*Math.sqrt(num),那么由较小的因子求较大的因子时，会重复，要排除这种情况
                if ( n != i ){      
                    //当然，此时num，不会出现这种情况。如果num=4，就会出现这种情况(比如2和2两个因子)
                    arr.add(n);     //将较大的因子放入arr数组
                }

            }

        }

        //System.out.println(arr.size());   //num一共有128个因子

        //三层for循环依次遍历即可。 128^3 = 2097152 计算机完全可以在短时间内算出结果
        int count = 0;
        for ( long i : arr ){
            for ( long j : arr ){
                for ( long k : arr ){
                    if ( i * j * k == num ){
                        count++;
                    }
                }
            }
        }
        System.out.println(count);

    }
}

题目：即约分数

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一个分数的分子和分母的最大公约数是 1，这个分数称为既约分数。

例如
$$
\frac{3}{4} ,\frac{1}{8} ,\frac{7}{1}
$$
， 都是既约分数。

请问，有多少个既约分数，分子和分母都是 1 到 2020 之间的整数（包括 1 和 2020）？

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Main {
    public static void main(String[] args) {
      int sum = 0;
      for(int i=1;i<=2020;i++){
        for(int j=1;j<=2020;j++){
          if(gcd(i,j) == 1){
            sum++;
          }
        }
      }
      System.out.println(sum);
    }
    public static int gcd(int x,int y){ //辗转相除法
      return y==0 ? x:gcd(y,x%y);
    }
}

题目：数列求值

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

给定数列 1, 1, 1, 3, 5, 9, 17,⋯，从第 4 项开始，每项都是前 3 项的和。

求第 20190324 项的最后 4 位数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main{
/*20190324 这个数过于庞大，无论是递归还是迭代，程序都无法正常运行，而且int、long、BigDecimal等都无法承载这么大的数
题目要求我们只取最后四位，那我们可以对每次运算出来的结果 %10000 这样每次结果就都保留最后四位数字*/
  public static void main(String[] args){
    int a=1,b=1,c=1,d=0;
    for(int i =4;i<=20190324;i++){
      d=(a+b+c)%10000;
      a=b; //注意这里的顺序很重要
      b=c;
      c=d;
    }
    System.out.println(d);
  }
}